#include "bellmanford.h"
#include <glib.h>

BellmanFord::~BellmanFord()
{
}

const char* BellmanFord::get_nome()
{
  return "Bellman-Ford";
}

guint BellmanFord::rilassa_archi(report_function report_func)
{
    ostringstream oss;
    GSList* temp = grafo_corrente->get_archi();
    guint archi_rilassati = 0;
    while(temp != NULL)
    {
      Arco* arco_corrente = ((Arco *) temp->data);
      Nodo* nodo = arco_corrente->get_origine();

	  // Relax
	  if(nodo->get_distanza() < G_MAXINT &&
	     nodo->get_distanza() + arco_corrente->get_lunghezza() < arco_corrente->get_destinazione()->get_distanza())
  	  {
        gint distanza_originale = arco_corrente->get_destinazione()->get_distanza();
        
        oss.str("");
        oss.clear();
        oss<<"\tRelax("<<nodo->get_indice()<<", "<<arco_corrente->get_destinazione()->get_indice()<<") da ";
        if(distanza_originale == G_MAXINT)
            oss<<"infinito";
        else
            oss<<distanza_originale;
        oss<<" a "<<(nodo->get_distanza()+arco_corrente->get_lunghezza())<<endl;
        report(report_func, oss.str().c_str());

  	    arco_corrente->get_destinazione()->set_distanza(nodo->get_distanza() + arco_corrente->get_lunghezza());
  	    arco_corrente->get_destinazione()->set_precedente(nodo);
  	    archi_rilassati++;
  	  } else
  	  {
            oss.str("");
            oss.clear();
            oss<<"\tRelax("<<nodo->get_indice()<<", "<<arco_corrente->get_destinazione()->get_indice()<<") non ha bisogno di rilassamento"<<endl;
            report(report_func, oss.str().c_str());	  
      }
      
      temp = g_slist_next(temp);
    }
    
    return archi_rilassati;
}

void BellmanFord::esegui(report_function report_func)
{
  clock_t start = clock();
  ostringstream oss;
// Inizializza le distanze

  report(report_func, "Inizializzo le distanze a infinito\n");
  grafo_corrente->prepara();

  for(guint iterazione=0; iterazione < grafo_corrente->get_numero_nodi(); iterazione++)
    rilassa_archi(report_func);
  
  // Esegue un ulteriore rilassamento degli archi per verificare se esiste un ciclo negativo
  if(rilassa_archi(NULL) > 0)
    report(report_func, "Individuato un ciclo negativo!\n");
  
  clock_t end = clock();
  gfloat secondi = (((gfloat)(end - start))/CLOCKS_PER_SEC);

  oss.str("");
  oss.clear();
  oss<<"Esecuzione terminata in ";  
  oss.precision(5);
  oss<<secondi<<" secondi"<<endl; 
  report(report_func, oss.str().c_str());  
}
